package features.advance.nowcoder.meituan;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

/**
 * @author LIN
 * @date 2021-05-20
 */
interface Sort{
    void sort(int[] arr);
}

/**
 * 插入排序
 */
class InsertSort implements Sort{
    @Override
    public void sort(int[] arr) {
        insertSort(arr);
    }

    public void insertSort(int[] nums){
        /*
        for j <- 2 to length[A]
            do key <- A[j]
                i <- j-1
                while i>0 and A[i]>key
                    do A[i+1] <- A[i] //
                    i<-i-1
                A[i+1] <- key
         */
        for(int j=1;j<nums.length;j++){
            int key = nums[j];
            int i = j-1;
            while(i>=0 && nums[i] > key){
//                int tmp = nums[i+1];
                nums[i+1] = nums[i];
//                nums[i] = tmp; 交换i和之后的元素
                i--;
            }
            nums[i+1] = key;
        }
    }

    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort() {
        };
        int[] nums = {49,38,65,97,76,13,27,49};
        System.out.println(Arrays.toString(nums));
        insertSort.insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

/**
 * 希尔排序
 * 每次比较排序间隔为gap的元素，逐渐缩小gap直到gap=1；
 */
class ShellSort implements Sort{
    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort() {
        };
        int[] nums = {3,2,4,6,2,5,7,3,56,8,9};
        System.out.println(Arrays.toString(nums));
        shellSort.shellSort(nums);
//        shellSort.shellInsertSort(nums,1);等同于插入排序
        System.out.println(Arrays.toString(nums));

    }
    @Override
    public void sort(int[] arr) {
        shellSort(arr);
    }

    public void shellSort(int[] nums){
        int dk = nums.length /2;
        while(dk > 0){
            shellInsertSort(nums, dk);
            dk /=2;
        }
    }

    private void shellInsertSort(int[] nums, int dk){
        /*
        特殊的插入排序，dk=1的时候，是普通的插入排序
         */
        /*
            插入排序的流程
            从第二元素，开始，一直循环到数组最后一个元素，每次循环，保证第一个元素到当前元素是递增的；
            每次循环的额操作：A[0-i],A[k]<=A[k+1](0<=k<=i)，循环i次，每次判断A[i]和当前元素，大的话，就把大的元素向后移动一位，
            最后将A[i]插入到合适的位置。

         */
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i-dk;
            while(j>=0 && nums[j]>key){
                nums[j+dk] = nums[j];
                j-=dk;
            }
            nums[j+dk] = key;
        }

    }
}

/**
 * 分治排序
 * 分治然后合并两个子数组
 */
class DivideAndConquerSort implements Sort{

    @Override
    public void sort(int[] arr) {
        mergeSort(arr,0,arr.length - 1);
    }

    public void mergeSort(int[] nums,int p,int r){
        if(p<r){
            int q = (p+r) / 2;
            mergeSort(nums, p, q);
            mergeSort(nums, q+1, r);
            merge(nums,p,q,r);
        }
    }
    public void merge(int[] nums,int p,int q,int r){
        System.out.println("["+p+","+q+"]==>["+(q+1)+","+r+"]");
        System.out.println(Arrays.toString(nums));
        int n1 = q-p+1;
        int n2 = r-q;
        int[] L = new int[n1+1];
        for (int i = 0; i < n1; i++) {
            L[i] = nums[p+i];
        }
        int[] R = new int[n2+1];
        for (int i = 0; i < n2; i++) {
            R[i] = nums[q+i+1];
        }
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;
        int li = 0, ri=0;
        for (int i = p; i <= r; i++) {
            if(L[li] <= R[ri]){
                nums[i] = L[li];
                li++;
            }else{
                nums[i] = R[ri];
                ri++;
            }
        }
        System.out.println(Arrays.toString(nums));


    }
    public static void main(String[] args) {
//        int[] arr1 = {1,2,3,4);
//        int[] arr2 = {6,7,8,9};
        int[] arr = {1,4,0,3,4,2,5,543,6,32};

        DivideAndConquerSort sort = new DivideAndConquerSort() {
        };
        sort.sort(arr);
//        int i1 = 0,i2 = 0;
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(i1+i2);
//
//
//            if(i1>=arr1.length){
//                arr[i] = arr2[i2++];
//                continue;
//            }
//            if(i2>=arr2.length){
//                arr[i] = arr1[i1++];
//                continue;
//            }
//            if(arr1[i1] < arr2[i2]){
//                arr[i] = arr1[i1];
//                i1++;
//            }else{
//                arr[i] = arr2[i2];
//                i2++;
//            }
//        }
        System.out.println(Arrays.toString(arr));
    }
}

/**
 * 桶排序
 */
class BucketSort implements Sort{

    @Override
    public void sort(int[] arr) {
        bucketSort(arr);
    }

    /**
     * 先获取数组最大值和最小值，根据最大最小值
     * @param arr
     */
    public void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //创建桶
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
        //将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        //对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
        // 还原排序后的数组
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            ArrayList<Integer> integers = bucketArr.get(i);
            for (int i1 = 0; i1 < integers.size(); i1++) {
                arr[index++] = integers.get(i1);
            }
        }
    }

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort() {
        };
        int[] nums = {2,7,5,3,3,57,22,31,22};
        System.out.println(Arrays.toString(nums));
        bucketSort.bucketSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}
/**
 * 快速排序
 */
class QuickSort implements Sort{
    /**
     * QUICKSORT(A,p,r)
     *  if p<r
     *      then q <- PARTITION(A，p,r)
     *          QUICKSORT(A,p,q-1)
     *          QUICKSORT(A,q+1,r)
     * 最初的调用是QUICKSORT(A,1,length[A])
     * q 选择的位置，q左边的是比q小的元素，右边是比q大的元素
     * @param arr
     */
    @Override
    public void sort(int[] arr) {
        quickSort(arr,0,arr.length-1);
    }

    public void quickSort(int[] nums,int p,int r){
        if(p<r){
            int q = partition(nums,p,r);
            quickSort(nums, p, q-1);
            quickSort(nums, q+1, r);
        }
    }

    private  void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 大于pos元素的在左边，小于pos元素的在右边
     * @param nums
     * @param p
     * @param r
     * @return
     */
    private int partition(int[] nums,int p,int r){
        /*
        PARTITION(A,p,r)
        x <- A[r]
        i <- p -1
        for j <- p to r-1
            do if A[j]<=x
                then i <- i+1
                    exchange A[i]<->A[j]
        exchange A[i+1]<->A[r]
        return i+1
         */
        int x = nums[r];
        int i = p-1; // 需要交换元素位置的下标，即小于pos元素的子数组的最右侧元素下标
        for (int j = p; j <= r; j++) {
            if(nums[j] <= x){ // >= 小于pos元素的值在左边，大于pos元素的值在右边
                i++;
                swap(nums,i,j);
            }
        }
        return i;
    }

    public static void main(String[] args) {
        int[] arr = {2,10,9,3,1,8,2,6,9};
        System.out.println(Arrays.toString(arr));
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] >= arr[arr.length - 1]){
                int tmp = arr[i];
                arr[i] = arr[index];
                arr[index] = tmp;
                System.out.println(index);
                index++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

/**
 * 堆排序
 */
class HeapSort implements Sort{
    // 创建大顶堆
    public void maxHeapify(int[] arr){
        for (int i = arr.length / 2 -1; i >= 0; i--) {
            int tmp = arr[i];
            // 遍历i的左子节点，根据左节点获取右节点，将大的值移动到前面，保证根大于所有子节点的值
            for(int k = i*2+1;k< arr.length;k=2*k+1) {
                if(k+1<arr.length && arr[k] < arr[k+1]){
                    k++;
                }
                if(arr[k] > tmp){
                    arr[i] = arr[k];
                    i = k;
                }else {
                    break;
                }
            }
            arr[i] = tmp;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {3,10,7,12,4,27,9,0,8,13,16,12,1,17};
        System.out.println(Arrays.toString(arr));
        new HeapSort().maxHeapify(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Override
    public  void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
public class BubbleSort implements Sort{

    // 装饰器模式
    private Sort sort;

    public BubbleSort(){
        this.sort = this;
    }

    public BubbleSort(Sort sort){
        this.sort = sort;
    }

    public void sort(int[] nums, String type){
        if(type == null){
            return;
        }
        if("quick".equals(type)){
            new QuickSort().sort(nums);
        }else if("heap".equals(type)){
            new HeapSort().sort(nums);
        }else{
            sort(nums);
        }
    }
    public static void main(String[] args) {
        int[] arr = {21, 8, 5, 11, 6, 22, 4, 3, 12, 7};

        Sort bubbleSort = new BubbleSort() {
            @Override
            public void bubbleSort(int[] arr) {
                int min = arr[0];
                int index = 0,k=0;
                for (int i = 0; i < arr.length-k; i++) {
                    for (int j = i+1; j < arr.length-k; j++) {
                        if(arr[i] < arr[j]){
                            int tmp = arr[i];
                            arr[i]=arr[j];
                            arr[j]=tmp;
                        }else {
                            //可以同时确认数组最小值，将最小值依次放到子数组最右侧
//                            System.out.print("("+arr[j]+","+j+")"+"===>("+(arr[i])+")===>");
                            if(min > arr[j]){
                                min = arr[j];
                                index = j;
//                                System.out.println("("+arr[j]+","+j+")");
                            }
                        }
                    }
//                    System.out.print(Arrays.toString(arr));
//                    System.out.print("===>");
                    if(i<arr.length - 1 - k && arr[index] < arr[arr.length - 1 - k]){
                        min = arr[0];
                        int tmp = arr[index];
                        arr[index]=arr[arr.length-1 - k];
                        arr[arr.length-1 - k]=tmp;
                        k++;
                    }
//                    System.out.println(Arrays.toString(arr));
                }

            }
        };
        int n = 1000000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            int i1 = new Random().nextInt(n);
            a[i] = i1;
//            System.out.println(Arrays.toString(a));

        }
        bubbleSort = new ShellSort();
        bubbleSort.sort(a);
        System.out.println(Arrays.toString(a));
//        Sort heapSort = new HeapSort();
//        heapSort.sort(a);
//        System.out.println(Arrays.toString(a));

    }

    public void bubbleSort(int[] arr){
        int flag = 0;
        int t = 0;
        for (int i = 0; i < arr.length; i++) {
            // 正向移动最大的元素到左侧
            for (int i2 = 0; i2 < arr.length-1-i; i2++) {
                if (arr[i2] < arr[i2+1]) {
                    int tmp = arr[i2+1];
                    arr[i2+1] = arr[i2];
                    arr[i2] = tmp;
                    flag = 1;
//                    System.out.println(i2);
                }
            }

            // 也可以实现排序，难优化
//            for (int i1 = i+1; i1 < arr.length; i1++) {
//               if(arr[i1] > arr[i]){
//                   int tmp = arr[i];
//                   arr[i] = arr[i1];
//                   arr[i1] = tmp;
//                   flag = 1;
//               }
//            }
            // 优化三
            // 反向移动最小的元素到右侧
            for (int j = arr.length - 1-i; j > 0; j--) {
                if(arr[j-1] < arr[j]){
                    int tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                    flag = 1;
                }
            }

            // 优化一
            // 如果第一次循环，一次也没交换位置，则说明已经有序
            if(flag == 0){
                return;
            }
        }
    }
    @Override
    public void sort(int[] arr){
        bubbleSort(arr);
    }
}
